#ifndef ARRAY_H
#define ARRAY_H

/**
 * \bibitem{thomas2009introduction}
 * T. H. Thomas, \textit{Introduction to algorithms}, 2009.
 */

#include <omp.h>
#include <vector>
#include "key.h"
#include "cell.h"
#include "table.h"
#include <malloc.h>

namespace RealScan
{

/*
 * Note: To ensure functionality, (for upper-level logic) `value == T()` means there is no cell at the current location.
 */

// Array representation of `Table`
template <typename T, unsigned THREADS_NUM = 12>
class Array : public Table<T>
{
public:
    // Constructor, `origin` indicates the minimum key.
    Array(std::size_t rows, std::size_t cols) :
        m_arr(rows * cols, T()), m_rows(rows), m_cols(cols) {}

    // Destructor
    ~Array() { std::vector<T>().swap(m_arr); malloc_trim(0); };

private:
    // The 1D array representing the grid map
    std::vector<T> m_arr;

    // Array shape
    std::size_t m_rows;
    std::size_t m_cols;

    // key -> index
    std::size_t index(const Key& key) const
    {
        return (key.x * m_cols + key.y); 
    }

    // Check if the key is valid to prevent out-of-bounds access
    bool isKeyValid(const Key& key) const
    {
        // Check if the key is within the valid range
        bool isWithinRows = (0 <= key.x && key.x < m_rows);
        bool isWithinCols = (0 <= key.y && key.y < m_cols);

        // Return true only if all conditions are satisfied
        return isWithinRows && isWithinCols;
    }

public:
    ////// `Table` interface implementation //////
    // Search
    std::optional<T> search(const Key& key) const override
    {
        // `key` is valid and the value exist (!= T())
        if (isKeyValid(key) && m_arr[index(key)] != T())
        {
            return m_arr[index(key)];
        }
        return std::nullopt;
    }

    // Insert
    bool insert(const Key& key, const T& value) override
    {
        if (isKeyValid(key))
        {
            // Set or change value
            m_arr[index(key)] = value;
            return true;
        }
        return false;
    }

    // Remove
    void remove(const Key& key) override
    {
        if (isKeyValid(key))
        {
            // Reset to `T()`
            m_arr[index(key)] = T();
        }
    }

    // Vectorize
    void toVector(std::vector<Cell<T> >& vec, const Key& minKey, const Key& maxKey) const override
    {
        // Check if the key range is valid
        if (!isKeyValid(minKey) || !isKeyValid(maxKey)) return;

        // Clear the vector
        vec.clear();

        #pragma omp parallel num_threads(THREADS_NUM)
        {
            std::vector<Cell<T>> localCells;

            // Parallel iteration over each row
            #pragma omp for nowait
            for (std::int32_t x = minKey.x; x <= maxKey.x; ++x)
            {
                for (std::int32_t y = minKey.y; y <= maxKey.y; ++y)
                {
                    // If the value exits, add it to the vector
                    if (m_arr[index({x, y})] != T())
                    {
                        localCells.push_back({{x, y}, m_arr[index({x, y})]});
                    }
                }
            }

            // Merge local cells into the main vector
            #pragma omp critical
            {
                vec.insert(vec.end(), localCells.begin(), localCells.end());
            }
        }
    }

    // cells number
    std::size_t size() const override
    {
        std::size_t size_ = 0;
        #pragma omp parallel
        {
            std::size_t localSize = 0;
            // Parallel iteration over rows
            #pragma omp for nowait
            for (std::size_t i = 0; i < m_rows; i++)
            {
                for (std::size_t j = 0; j < m_cols; j++)
                {
                    if (m_arr[i * m_cols + j] != T()) localSize++;
                }
            }

            #pragma omp critical
            {
                size_ += localSize;
            }   
        }
        return size_;
    }

    // memory used, const there
    std::size_t space() const override
    {
        return  sizeof(m_arr) + m_arr.size() * sizeof(T);
    }

}; 


} /* RealScan */

#endif /* ARRAY_H */